﻿#include <iostream>

static int walkRecur(int N, int S, int E, int cur, int remain)
{
    if (cur < 1 || cur > N) return 0;

    if (remain == 0)
    {
        return cur == E ? 1 : 0;
    }

    int moveLeft = 0;
    if (cur > 1)
    {
        moveLeft = walkRecur(N, S, E, cur - 1, remain - 1);
    }

    int moveRight = 0;
    if (cur < N)
    {
        moveRight = walkRecur(N, S, E, cur + 1, remain - 1);
    }

    return moveLeft + moveRight;
}

static int byStrictTable(int N, int S, int E, int stepCount)
{
    int indexSize = N + 1;
    int stepCountSize = stepCount + 1;
    int* dp = (int*)malloc(indexSize * stepCountSize * sizeof(int));
    memset(dp, 0, indexSize * stepCountSize * sizeof(int));

    // dp(index, remain) = dp[index + remain * indexSize]

    dp[E] = 1;
    for (int remain = 1; remain < stepCountSize; remain++)
    {
        for (int cur = 1; cur < indexSize; cur++)
        {
            int moveLeft = cur > 1 ? dp[cur - 1 + (remain - 1) * indexSize] : 0;
            int moveRight = cur < N ? dp[cur + 1 + (remain - 1) * indexSize] : 0;
            dp[cur + remain * indexSize] = moveLeft + moveRight;
        }
    }

    int res = dp[S + stepCount * indexSize];
    free(dp);
    return res;
}

// 给一个正整数N(N > 1)，代表有N个位置; 再给一个正整数S，表示开始位置(1~N);
// 再给一个正整数E，表示去往哪个位置(1~N); 再给一个正整数K，表示从S移动到E，需要移动K步。
// 机器人每次移动一个位置，可以向左，也可以向右，但是，如果机器人来到1位置，那么它下一步只能走到2；
// 如果来到N位置，那么它下一步只能走到N - 1.
// 问：当从S走到E，必须走K步的情况下，有多少种方法 ?
// 举例：N = 5，S = 2，E = 4，K = 4
// 1  2  3  4  5
// ↑     ○
// 方法1 : 2->3->4->5->4
// 方法2 : 2->3->4->3->4
// 方法3 : 2->3->2->3->4
// 方法4 : 2->1->2->3->4
int main_StepToEByK()
{
    int N = 5;
    int S = 1;
    int E = 5;
    int stepCount = 10;
    int methodCount = walkRecur(N, S, E, S, stepCount);
    int byStrictTableValue = byStrictTable(N, S, E, stepCount);
    printf("%d,%d\n", methodCount, byStrictTableValue);

    return 0;
}